Dr. J's Maths.com
Where the techniques of Maths
are explained in simple terms.

Networks and Graph Theory - Minimum Spanning Trees.
Test Yourself 1 - Solutions.


 

Remember - with minumum spanning trees, we are including all vertices but looking for the minimum sum of the weights on the edges.

Using Kruskal's algorithm.

1.

Prepare a Kruskal's table (we were not given a starting point).

DF 1
CD 2
DE 4
CF 5 (cycle)
DG 5
AB 6
FE 7 (cycle)
EG 8 (cycle)
BF 9
The minimum spanning tree is shown below:

 

The minimum weight of the spanning tree is 27.
  2.

Prepare a Kruskal's table (we were not given a starting point).

BE 2
DE 2
BA 4.
(follows selection of EC)
BD 6
EC 3
CA 10

The minimum spanning tree is shown below:

 

The minimum weight of the spanning tree is 11.
 

3.

As no starting point has been given, we use Kruskal's algorithm. Start with the smallest edge (here CD).

CD 10
AD 15
GH 18
BG 18
EH 20
AC 20
EG 24
BD 30
AB 32
CF 42
FE 45

The total length is 180 m. Hence the cost of the cables is $9,000.

The minimum spanning tree to include every holiday cabin is

  4.
Step 1: Write down the edge with the smallest weight.    
  EG 1
Step 2: Write down the edges with the next smallest weight and continue adding edges with increasing weight.    
Drawing edges on a network diagram as you accept them. GH 2
  FC 2
  AB 4
  CH 4
Cannot add FG as it forms a cycle. FG 6
Cannot add EF as it forms a cycle. EF 7
  CD 7
  BC 8
Cannot add AE as it forms a cycle. AE 8
This link joins all vertices as required. DJ 9
Do not require any more edges. HJ 10

 

 The minimum spanning tree is:

Minimum weight is 37.
 

5.

 

Edge Weight between vertices Weight from start Explanation
ED 5 5 The smallest edge is ED - so start with that.
DA 10/15 15 (min)

From D we can go to A or C.

DC is smaller to take that.
DC 8 13
CB 11/14 24 (min) From C we can go to B.
But DA (in row 2) is smaller so take that edge.
AB 12 27 CB (11) is shorter than AB (12).

The spanning network has a length of 34 kms
(5 + 8 + 11 + 10 = 34).
  6.
Path Kms Comment
RL 17 Start with the shortest kms.
RQ 20  
LQ 25 Creates a cycle.
PO 25 Include
ON 26 Include
QP 27 Include
PM 27 Include
MN 29 Do not need.

 

The spanning network has a length of 142 kms.
  7.  
  8.

(i) The values should be chosen so that:

  • the value for AE is greater than the value for AB (600).
  • the value for BC (and so for CB) is greater than the value for BD (500).

(ii) If AE has a greater value than AB, it would be excluded from the path at the first stage. It could not come back in later as it would then create a cycle.

If BC has a greater value than BD, it would be excluded from the path at the second stage. It could not come back in later as it would then create a cycle.

    Using Prim's algorithm.

 

9.

(i) Starting at vertex C:

Step 1: Write down all the edges coming from the starting point C.    
  CB 2
  CE 2
  CF 4
  CD 3
  CA 4
Step 2: Select CB (=2) and then
CE (=2). Then add the edges coming from B and E.		    
  BA 4
  EF 3
Step 3: Select the minimum weight
(CD = 3 but it could have been EF).
Then add the edges coming from D.		    
  DF 3
Step 4: Select the minimum weight
(EF = 3 but it could have been DF). All possible edges from F are already included..		    

Step 5: Select the minimum weight
which does not create a cycle -
CA (=4) is chosen (it could have been BA).
That defines the minimum spanning tree as all vertices are included.

Now add the weights:

Network weight = 2+2+3+3+4 = 14.

    

(ii) Starting at vertex E:

 

Weight of this network is also 14 and it is drawn the same.
Step 1: Write down all the edges coming from the starting point E.    
  EC 2
  EF 3
Step 2: Select CE (=2). Then add the edges coming from C.    
  CB 2
  CA 4
  CD 3
Step 3: Select the minimum weight
(CB = 2). Then add the edges coming from B.		    
  BA 4

Step 4: Select the minimum weight
(EF = 3 but it could have been CD).
Then add the edges coming from F
(FC cannot be added because it would from a cycle).

   
  FD 3
Step 5: Select the minimum weight
which does not create a cycle
(CD = 3 but it could have been FD).
There are no possible edges coming from D 		   
Step 6: Select the minimum weight
which does not create a cycle -
CA (=4) is chosen. That defines the minimum spanning tree as all vertices are included.		    

Now add the weights:

2+2+3+3+4 = 14.

    
10.
  A B C D
A   650   280
B 650   500 220
C   500   340
D 280 220 340  

Draw a picture!!

Prepare a Prim's table (we were given a starting place):

AB 650
AD 280
DB 220
DC 340
BC 500

Note: the blue values are the shortest paths from that vertex.

(i) Shortest path, starting at A, is 1,000 metres.

(ii) The route for the truck is A-D-B-C.

11.

Tap-P1 3
P1P2 5
P1P3 5
P2P5 3
P2P7 6
P3P4 3
P5P6 4
P4P6 5
P6P8 2
P8P7 8

NOTE: the P2P7 edge is not considered until the last choice (i.e. against P8P7) as it is not the smallest edge from P2.

The length of piping required is 31 metres.

12. Same diagram as for Q4 but the starting point is now J.
Step 1: Starting at J there are two edges: JD 9
  JH 10
Step 2: Select the smallest (JD) then list the edges flowing from D. DC 7
  DH 14
Step 3: Select DC and list edges from C. CB 8
  CF 2
  CH 4
Step 4: Select CF (2) and list edges flowing from F. FE 7
  FG 6
Step 5: The smallest (unselected) edge in the list is CH. Select CH and list edges flowing from H. HG 2
Step 6: Select HG and list edes from G GE 1
Step 7: Select GE and list edges from E. EA 8
  EB 11
Step 8: Select one of the two smallest weights of 8 - CB or EA.    
Same diagram (if BC is chosen) and a total weight of 37.

13.

 

  
14.  
15.  
16.  

17. (i) Using Kruskal, the minimum spanning tree has a weight of 39 and is as follows:

 (ii) Using Prim and starting at vertex E, the minimum spanning tree has a weight of 41 and is as follows: